home *** CD-ROM | disk | FTP | other *** search
/ BBS Toolkit / BBS Toolkit.iso / doors_1 / doorskl3.zip / XBBSMSG.ZIP / XBBSLZSS.C < prev    next >
C/C++ Source or Header  |  1991-12-09  |  21KB  |  840 lines
  1. /**************************************************************
  2.     lzhuf.c
  3.     written by Haruyasu Yoshizaki 1988/11/20
  4.     some minor changes 1989/04/06
  5.     comments translated by Haruhiko Okumura 1989/04/07
  6.     This stuff is pretty much the original article, but
  7.     M. Kimes hacked on it in June of 1990
  8.     Screwed with everything to work with XBBS msg bases
  9.     Under OS/2 (define OS2) this code works like a resource,
  10.     locking one requesting process until another has finished
  11.     if already in use.  Not reentrant except under OS/2 as above.
  12. **************************************************************/
  13.  
  14. #ifdef OS2
  15.     #define INCL_DOS
  16.     #include <os2.h>
  17. #endif
  18.  
  19. #include <stdlib.h>
  20. #include <string.h>
  21. #include <stdio.h>
  22. #include "xmsg.h"
  23.  
  24. static int  _fastcall Encode (void);
  25. static int  _fastcall Decode (void);
  26. static int  _fastcall GetBit (void);
  27. static int  _fastcall GetByte (void);
  28. static void _fastcall InitTree (void);            /* initialize trees */
  29. static void _fastcall InsertNode (int r);         /* insert to tree */
  30. static void _fastcall DeleteNode (int p);         /* remove from tree */
  31. static void _fastcall StartHuff (void);           /* init tree */
  32. static void _fastcall EncodeChar (unsigned c);
  33. static void _fastcall EncodePosition (unsigned c);
  34. static void _fastcall EncodeEnd (void);
  35. static int  _fastcall DecodeChar (void);
  36. static int  _fastcall DecodePosition (void);
  37. static void _fastcall Putcode (int l, unsigned c);
  38. static void _fastcall Lupdate (int c);
  39. static int  _fastcall alloc_stuff (void);
  40. static void _fastcall free_stuff (void);
  41.  
  42. /********** LZSS compression **********/
  43.  
  44. #define N           4096        /* buffer size */
  45. #define F           60             /* lookahead buffer size */
  46. #define THRESHOLD   2
  47. #define NIL         N              /* leaf of tree */
  48.  
  49. typedef unsigned char uchar;
  50. typedef unsigned int  word;
  51.  
  52. static unsigned      getbuf;
  53. static uchar         getlen;
  54. static unsigned      putbuf;
  55. static uchar         putlen;
  56. static unsigned int  bytesdone, bytestodo;
  57. static int           match_position, match_length;
  58. static unsigned char *text_buf;
  59. static int           *lson;
  60. static int           *rson;
  61. static int           *dad;
  62. static char          *inbuf;
  63. static char          *outbuf;
  64. static unsigned int  textsize, codesize;
  65.  
  66. #ifdef OS2
  67.     static unsigned long lzssSEM = 0L;
  68. #endif
  69.  
  70. /* external functions */
  71.  
  72. extern char * _fastcall rstrip (char *a);
  73. extern char * _fastcall lstrip (char *a);
  74. extern char * _fastcall stripcr (char *a);
  75.  
  76.  
  77.  
  78. int _fastcall Encode (void)  { /* compression */
  79.  
  80.     int          i, c, len, r, s, last_match_length;
  81.     unsigned int printcount = 0;
  82.  
  83.  
  84.  
  85.     if(!alloc_stuff()) {
  86.         return 0;
  87.     }
  88.     codesize = bytesdone = textsize = 0;
  89.     StartHuff();
  90.     InitTree();
  91.     s = 0;
  92.     r = N - F;
  93.     for (i = s; i < r; i++) {
  94.         text_buf[i]=0x20;
  95.     }
  96.     for (len = 0; len < F; len++) {
  97.         c=(int) *inbuf;
  98.         if(!c) break;
  99.         inbuf++;
  100.         bytesdone++;
  101.         if(bytesdone>bytestodo) break;
  102.         text_buf[r+len]=c;
  103.     }
  104.     textsize = len;
  105.     for (i = 1; i <= F; i++) InsertNode(r - i);
  106.     InsertNode(r);
  107.     do {
  108.         if (match_length > len)
  109.             match_length = len;
  110.         if (match_length <= THRESHOLD) {
  111.             match_length = 1;
  112.             EncodeChar(text_buf[r]);
  113.         } else {
  114.             EncodeChar(255 - THRESHOLD + match_length);
  115.             EncodePosition(match_position);
  116.         }
  117.         last_match_length = match_length;
  118.         for (i = 0; i < last_match_length; i++) {
  119.             c=(int)*inbuf;
  120.             if(!c) break;
  121.             inbuf++;
  122.             bytesdone++;
  123.             if(bytesdone>bytestodo) break;
  124.             DeleteNode(s);
  125.             text_buf[s] = c;
  126.             if (s < F - 1)
  127.                 text_buf[s + N] = c;
  128.             s = (s + 1) & (N - 1);
  129.             r = (r + 1) & (N - 1);
  130.             InsertNode(r);
  131.         }
  132. /*
  133.         if ((textsize += i) > printcount) {
  134.             printcount += 1024;
  135.         }
  136. */
  137.         while (i++ < last_match_length) {
  138.             DeleteNode(s);
  139.             s = (s + 1) & (N - 1);
  140.             r = (r + 1) & (N - 1);
  141.             if (--len) InsertNode(r);
  142.         }
  143.     } while (len > 0);
  144. EndIt:
  145.     EncodeEnd();
  146.     free_stuff();
  147.     return 1;
  148. }
  149.  
  150.  
  151. int _fastcall Decode (void)  { /* recover */
  152.  
  153.     int          i, j, k, r, c;
  154.     unsigned int count;
  155.     unsigned int printcount = 0;
  156.  
  157.  
  158.     codesize = 0;
  159.     if (textsize < 1024) {
  160.         return 0;
  161.     }
  162.  
  163.     if(!alloc_stuff()) {
  164.         return 0;
  165.     }
  166.  
  167.     StartHuff();
  168.     for (i = 0; i < N - F; i++) text_buf[i]=0x20;
  169.     r = N - F;
  170.     for (count = 0; count < textsize; ) {
  171.         c = DecodeChar();
  172.         if (c < 256) {
  173.             *outbuf=(char)c;
  174.             outbuf++;
  175.             text_buf[r++] = c;
  176.             r &= (N - 1);
  177.             count++;
  178.         }
  179.         else {
  180.             i = (r - DecodePosition() - 1) & (N - 1);
  181.             j = c - 255 + THRESHOLD;
  182.             for (k = 0; k < j; k++) {
  183.                 c = text_buf[(i + k) & (N - 1)];
  184.                 *outbuf=(char)c;
  185.                 outbuf++;
  186.                 text_buf[r++] = c;
  187.                 r &= (N - 1);
  188.                 count++;
  189.             }
  190.         }
  191. /*
  192.         if (count > printcount) {
  193.             printcount += 1023;
  194.         }
  195. */
  196.     }
  197.     free_stuff();
  198.     return 1;
  199. }
  200.  
  201.  
  202. static void _fastcall InitTree (void) { /* initialize trees */
  203.  
  204.     int  i;
  205.  
  206.  
  207.     for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;    /* root */
  208.     for (i = 0; i < N; i++) dad[i] = NIL;                /* node */
  209. }
  210.  
  211.  
  212. static void _fastcall InsertNode (int r) { /* insert to tree */
  213.  
  214.     int           i, p, cmp;
  215.     unsigned char *key;
  216.     unsigned      c;
  217.  
  218.  
  219.     cmp = 1;
  220.     key = &text_buf[r];
  221.     p = N + 1 + key[0];
  222.     rson[r] = lson[r] = NIL;
  223.     match_length = 0;
  224.     for ( ; ; ) {
  225.         if (cmp >= 0) {
  226.             if (rson[p] != NIL)
  227.                 p = rson[p];
  228.             else {
  229.                 rson[p] = r;
  230.                 dad[r] = p;
  231.                 return;
  232.             }
  233.         } else {
  234.             if (lson[p] != NIL)
  235.                 p = lson[p];
  236.             else {
  237.                 lson[p] = r;
  238.                 dad[r] = p;
  239.                 return;
  240.             }
  241.         }
  242.         for (i = 1; i < F; i++)
  243.             if ((cmp = key[i] - text_buf[p + i]) != 0)
  244.                 break;
  245.         if (i > THRESHOLD) {
  246.             if (i > match_length) {
  247.                 match_position = ((r - p) & (N - 1)) - 1;
  248.                 if ((match_length = i) >= F)
  249.                     break;
  250.             }
  251.             if (i == match_length) {
  252.                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  253.                     match_position = c;
  254.                 }
  255.             }
  256.         }
  257.     }
  258.     dad[r] = dad[p];
  259.     lson[r] = lson[p];
  260.     rson[r] = rson[p];
  261.     dad[lson[p]] = r;
  262.     dad[rson[p]] = r;
  263.     if (rson[dad[p]] == p)
  264.         rson[dad[p]] = r;
  265.     else
  266.         lson[dad[p]] = r;
  267.     dad[p] = NIL; /* remove p */
  268. }
  269.  
  270. static void _fastcall DeleteNode (int p) { /* remove from tree */
  271.  
  272.     int q;
  273.  
  274.  
  275.     if (dad[p] == NIL)
  276.         return;         /* not registered */
  277.     if (rson[p] == NIL)
  278.         q = lson[p];
  279.     else
  280.     if (lson[p] == NIL)
  281.         q = rson[p];
  282.     else {
  283.         q = lson[p];
  284.         if (rson[q] != NIL) {
  285.             do {
  286.                 q = rson[q];
  287.             } while (rson[q] != NIL);
  288.             rson[dad[q]] = lson[q];
  289.             dad[lson[q]] = dad[q];
  290.             lson[q] = lson[p];
  291.             dad[lson[p]] = q;
  292.         }
  293.         rson[q] = rson[p];
  294.         dad[rson[p]] = q;
  295.     }
  296.     dad[q] = dad[p];
  297.     if (rson[dad[p]] == p)
  298.         rson[dad[p]] = q;
  299.     else
  300.         lson[dad[p]] = q;
  301.     dad[p] = NIL;
  302. }
  303.  
  304. /* Huffman coding */
  305.  
  306. #define N_CHAR   (256 - THRESHOLD + F)
  307.                  /* kinds of characters (character code = 0..N_CHAR-1) */
  308. #define T        (N_CHAR * 2 - 1)    /* size of table */
  309. #define R        (T - 1)         /* position of root */
  310. #define MAX_FREQ 0x8000      /* updates tree when the */
  311.                  /* root frequency comes to this value. */
  312.  
  313.  
  314. /* table for encoding and decoding the upper 6 bits of position */
  315.  
  316. /* for encoding */
  317. uchar p_len[64] = {
  318.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  319.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  320.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  321.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  322.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  323.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  324.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  325.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  326. };
  327.  
  328. uchar p_code[64] = {
  329.     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  330.     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  331.     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  332.     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  333.     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  334.     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  335.     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  336.     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  337. };
  338.  
  339. /* for decoding */
  340. uchar d_code[256] = {
  341.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  342.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  343.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  344.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  345.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  346.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  347.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  348.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  349.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  350.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  351.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  352.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  353.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  354.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  355.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  356.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  357.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  358.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  359.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  360.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  361.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  362.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  363.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  364.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  365.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  366.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  367.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  368.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  369.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  370.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  371.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  372.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  373. };
  374.  
  375. uchar d_len[256] = {
  376.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  377.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  378.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  379.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  380.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  381.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  382.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  383.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  384.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  385.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  386.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  387.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  388.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  389.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  390.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  391.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  392.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  393.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  394.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  395.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  396.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  397.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  398.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  399.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  400.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  401.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  402.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  403.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  404.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  405.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  406.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  407.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  408. };
  409.  
  410. unsigned freq[T + 1]; /* frequency table */
  411.  
  412. int prnt[T + N_CHAR]; /* pointers to parent nodes, except for the */
  413.             /* elements [T..T + N_CHAR - 1] which are used to get */
  414.             /* the positions of leaves corresponding to the codes. */
  415.  
  416. int son[T]; /* pointers to child nodes (son[], son[] + 1) */
  417.  
  418.  
  419. static int _fastcall GetBit (void) {    /* get one bit */
  420.  
  421.     unsigned i;
  422.  
  423.  
  424.     while (getlen <= 8) {
  425.         if ((int)(i = (int)*inbuf) < 0) i = 0;
  426.         inbuf++;
  427.         bytesdone++;
  428.         getbuf |= i << (8 - getlen);
  429.         getlen += 8;
  430.     }
  431.     i = getbuf;
  432.     getbuf <<= 1;
  433.     getlen--;
  434.     return (int)((i & 0x8000) >> 15);
  435. }
  436.  
  437. static int _fastcall GetByte (void) {   /* get one byte */
  438.  
  439.     unsigned i;
  440.  
  441.  
  442.     while (getlen <= 8) {
  443.         if ((int)(i = (int)*inbuf) < 0) i = 0;
  444.         inbuf++;
  445.         bytesdone++;
  446.         getbuf |= i << (8 - getlen);
  447.         getlen += 8;
  448.     }
  449.     i = getbuf;
  450.     getbuf <<= 8;
  451.     getlen -= 8;
  452.     return (int)((i & 0xff00) >> 8);
  453. }
  454.  
  455.  
  456.  
  457. static void _fastcall Putcode (int l, unsigned c) {    /* output c bits of code */
  458.  
  459.     putbuf |= c >> putlen;
  460.     if ((putlen += l) >= 8) {
  461.         *outbuf=(char)(putbuf >> 8);
  462.         outbuf++;
  463.         if ((putlen -= 8) >= 8) {
  464.             *outbuf=(char)putbuf;
  465.             outbuf++;
  466.             codesize += 2;
  467.             putlen -= 8;
  468.             putbuf = c << (l - putlen);
  469.         } else {
  470.             putbuf <<= 8;
  471.             codesize++;
  472.         }
  473.     }
  474. }
  475.  
  476.  
  477. /* initialization of tree */
  478.  
  479. static void _fastcall StartHuff (void) {
  480.  
  481.     int i, j;
  482.  
  483.  
  484.     for (i = 0; i < N_CHAR; i++) {
  485.         freq[i] = 1;
  486.         son[i] = i + T;
  487.         prnt[i + T] = i;
  488.     }
  489.     i = 0; j = N_CHAR;
  490.     while (j <= R) {
  491.         freq[j] = freq[i] + freq[i + 1];
  492.         son[j] = i;
  493.         prnt[i] = prnt[i + 1] = j;
  494.         i += 2; j++;
  495.     }
  496.     freq[T] = 0xffff;
  497.     prnt[R] = 0;
  498.     putbuf=getbuf=0;
  499.     putlen=getlen=0;
  500. }
  501.  
  502.  
  503. /* reconstruction of tree */
  504.  
  505. static void _fastcall reconst (void) {
  506.  
  507.     int      i, j, k;
  508.     unsigned f, l;
  509.  
  510.  
  511.     /* collect leaf nodes in the first half of the table */
  512.     /* and replace the freq by (freq + 1) / 2. */
  513.  
  514.     j = 0;
  515.     for (i = 0; i < T; i++) {
  516.         if (son[i] >= T) {
  517.             freq[j] = (freq[i] + 1) / 2;
  518.             son[j] = son[i];
  519.             j++;
  520.         }
  521.     }
  522.     /* begin constructing tree by connecting sons */
  523.     for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  524.         k = i + 1;
  525.         f = freq[j] = freq[i] + freq[k];
  526.         for (k = j - 1; f < freq[k]; k--);
  527.         k++;
  528.         l = (j - k) * 2;
  529.         memmove(&freq[k + 1], &freq[k], l);
  530.         freq[k] = f;
  531.         memmove(&son[k + 1], &son[k], l);
  532.         son[k] = i;
  533.     }
  534.     /* connect prnt */
  535.     for (i = 0; i < T; i++) {
  536.         if ((k = son[i]) >= T) {
  537.             prnt[k] = i;
  538.         } else {
  539.             prnt[k] = prnt[k + 1] = i;
  540.         }
  541.     }
  542. }
  543.  
  544.  
  545. /* increment frequency of given code by one, and update tree */
  546.  
  547. static void _fastcall Lupdate (int c) {
  548.  
  549.     int i, j, k, l;
  550.  
  551.  
  552.     if (freq[R] == MAX_FREQ) {
  553.         reconst();
  554.     }
  555.     c = prnt[c + T];
  556.     do {
  557.         k = ++freq[c];
  558.  
  559.         /* if the order is disturbed, exchange nodes */
  560.         if (k > freq[l = c + 1]) {
  561.             while (k > freq[++l]);
  562.             l--;
  563.             freq[c] = freq[l];
  564.             freq[l] = k;
  565.  
  566.             i = son[c];
  567.             prnt[i] = l;
  568.             if (i < T) prnt[i + 1] = l;
  569.  
  570.             j = son[l];
  571.             son[l] = i;
  572.  
  573.             prnt[j] = c;
  574.             if (j < T) prnt[j + 1] = c;
  575.             son[c] = j;
  576.  
  577.             c = l;
  578.         }
  579.     } while ((c = prnt[c]) != 0); /* repeat up to root */
  580. }
  581.  
  582. unsigned code, len;
  583.  
  584. static void _fastcall EncodeChar (unsigned c) {
  585.  
  586.     unsigned i;
  587.     int      j, k;
  588.  
  589.  
  590.     i = 0;
  591.     j = 0;
  592.     k = prnt[c + T];
  593.  
  594.     /* travel from leaf to root */
  595.     do {
  596.         i >>= 1;
  597.  
  598.         /* if node's address is odd-numbered, choose bigger brother node */
  599.         if (k & 1) i += 0x8000;
  600.  
  601.         j++;
  602.     } while ((k = prnt[k]) != R);
  603.     Putcode(j, i);
  604.     code = i;
  605.     len = j;
  606.     Lupdate(c);
  607. }
  608.  
  609. static void _fastcall EncodePosition (unsigned c) {
  610.  
  611.     unsigned i;
  612.  
  613.  
  614.     /* output upper 6 bits by table lookup */
  615.  
  616.     i = c >> 6;
  617.     Putcode(p_len[i], (unsigned)p_code[i] << 8);
  618.  
  619.     /* output lower 6 bits verbatim */
  620.  
  621.     Putcode(6, (c & 0x3f) << 10);
  622. }
  623.  
  624. static void _fastcall EncodeEnd (void) {
  625.  
  626.     if (putlen) {
  627.         *outbuf=(char)(putbuf >> 8);
  628.         outbuf++;
  629.         codesize++;
  630.     }
  631. }
  632.  
  633. static int _fastcall DecodeChar (void) {
  634.  
  635.     unsigned c;
  636.  
  637.  
  638.     c = son[R];
  639.  
  640.     /* travel from root to leaf, */
  641.     /* choosing the smaller child node (son[]) if the read bit is 0, */
  642.     /* the bigger (son[]+1} if 1 */
  643.  
  644.     while (c < T) {
  645.         c += GetBit();
  646.         c = son[c];
  647.  
  648.     }
  649.     c -= T;
  650.     Lupdate(c);
  651.     return (int)c;
  652. }
  653.  
  654. static int _fastcall DecodePosition (void) {
  655.  
  656.     unsigned i, j, c;
  657.  
  658.  
  659.     /* recover upper 6 bits from table */
  660.  
  661.     i = GetByte();
  662.     c = (unsigned)d_code[i] << 6;
  663.     j = d_len[i];
  664.  
  665.     /* read lower 6 bits verbatim */
  666.  
  667.     j -= 2;
  668.     while (j--) {
  669.         i = (i << 1) + GetBit();
  670.     }
  671.     return (int)(c | (i & 0x3f));
  672. }
  673.  
  674.  
  675. char * _fastcall unpack_msg (XMSG *msg,char **hold) {
  676.  
  677.     char        *pp;
  678.     static char *tempbuf;
  679.  
  680.  
  681. #ifdef OS2
  682.     DosSemRequest(&lzssSEM,-1L);
  683. #endif
  684.  
  685.     pp = *hold;
  686.     *hold = NULL;
  687.     textsize = (word)atol(pp);
  688.     if(textsize < 1024) {
  689.         if(pp) free(pp);
  690. #ifdef OS2
  691.         DosSemClear(&lzssSEM);
  692. #endif
  693.         return NULL;
  694.     }
  695.     tempbuf = pp;
  696.     while(*tempbuf && *tempbuf != '\r') tempbuf++;
  697.     if(*tempbuf == '\r') tempbuf++;
  698.     else goto Grunged;
  699.     while(*tempbuf && *tempbuf != '\r') tempbuf++;
  700.     if(*tempbuf == '\r') tempbuf++;
  701.     else goto Grunged;
  702.     while(*tempbuf && *tempbuf != '\r') tempbuf++;
  703.     if(*tempbuf == '\r') tempbuf++;
  704.     else {
  705. Grunged:
  706.         if(pp) free(pp);
  707. #ifdef OS2
  708.         DosSemClear(&lzssSEM);
  709. #endif
  710.         return NULL;
  711.     }
  712.     inbuf = tempbuf;
  713.     outbuf = (char *)malloc((unsigned)(sizeof(char) * textsize) + 257);
  714.     if(!outbuf) {
  715.         if(pp) free(pp);
  716. #ifdef OS2
  717.         DosSemClear(&lzssSEM);
  718. #endif
  719.         return NULL;
  720.     }
  721.     tempbuf = outbuf;
  722.     if(!Decode()){
  723.         if(tempbuf) free(tempbuf);
  724.         tempbuf = NULL;
  725.     }
  726.     else tempbuf[textsize - 1] = 0;
  727.     if(pp) free(pp);
  728.     *hold = tempbuf;
  729. #ifdef OS2
  730.     DosSemClear(&lzssSEM);
  731. #endif
  732.     return tempbuf;
  733. }
  734.  
  735.  
  736. char * _fastcall pack_msg (XMSG *msg,char *hold) {
  737.  
  738.     char         *tempo;
  739.     char         lastmsgid[80] = "";
  740.     char         lastreply[80] = "";
  741.     unsigned int temp;
  742.     static char  *tempbuf;
  743.     char         textlen[18];
  744.  
  745.  
  746.   if(strlen(hold) < 1024) {
  747.     return NULL;    /* Too small to jack with */
  748.   }
  749.  
  750. #ifdef OS2
  751.   DosSemRequest(&lzssSEM,-1L);
  752. #endif
  753.  
  754.   if(tempo = strstr(hold,"\01MSGID:")) {
  755.     strncpy(lastmsgid,&tempo[7],80);
  756.     lastmsgid[79] = 0;
  757.     tempo = strchr(lastmsgid,'\r');
  758.     if(tempo) *tempo = 0;
  759.     lstrip(lastmsgid);
  760.     rstrip(lastmsgid);
  761.   }
  762.   else *lastmsgid = 0;
  763.  
  764.   if(tempo = strstr(hold,"\01REPLY:")) {
  765.     strncpy(lastreply,&tempo[7],80);
  766.     lastreply[79] = 0;
  767.     tempo = strchr(lastreply,'\r');
  768.     if(tempo) *tempo = 0;
  769.     lstrip(lastreply);
  770.     rstrip(lastreply);
  771.   }
  772.   else *lastreply = 0;
  773.  
  774.   textsize = strlen(hold);
  775.   bytestodo = textsize;
  776.   sprintf(textlen,"%01u",bytestodo);
  777.   tempbuf = (char *)malloc((textsize) + 257) + (strlen(lastmsgid) + 2)+
  778.                            (strlen(lastreply) + 2) + (strlen(textlen) + 2));
  779.   if(!tempbuf) {
  780.     free(hold);
  781. #ifdef OS2
  782.     DosSemClear(&lzssSEM);
  783. #endif
  784.     return NULL;
  785.   }
  786.  
  787.   temp = sprintf(hold,"%s\r%s\r%s\r",textlen,lastmsgid,lastreply);
  788.   outbuf = &tempbuf[temp];
  789.   inbuf = hold;
  790.   if(!Encode()) {
  791.     free(tempbuf);
  792.     free(hold);
  793. #ifdef OS2
  794.     DosSemClear(&lzssSEM);
  795. #endif
  796.     return NULL;
  797.   }
  798.   if(hold) free(hold);
  799.   hold = tempbuf;
  800.   msg->length = temp + codesize + 1;
  801. #ifdef OS2
  802.   DosSemClear(&lzssSEM);
  803. #endif
  804.   return hold;
  805. }
  806.  
  807.  
  808. static int _fastcall alloc_stuff (void) {
  809.  
  810.     text_buf = (unsigned char *)malloc(sizeof(char) * (N + F - 1));
  811.     if(!text_buf) return 0;
  812.     lson = (int *)malloc(sizeof(int) * (N + 1));
  813.     if(!lson) {
  814.         free(text_buf);
  815.         return 0;
  816.     }
  817.     rson = (int *)malloc(sizeof(int) * (N + 257));
  818.     if(!rson) {
  819.         free(text_buf);
  820.         free(lson);
  821.         return 0;
  822.     }
  823.     dad = (int *)malloc(sizeof(int) * (N + 1));
  824.     if(!dad) {
  825.         free(text_buf);
  826.         free(lson);
  827.         free(rson);
  828.         return 0;
  829.     }
  830.     return 1;
  831. }
  832.  
  833. void _fastcall free_stuff (void) {
  834.  
  835.     free(text_buf);
  836.     free(lson);
  837.     free(rson);
  838.     free(dad);
  839. }
  840.